"""
难度：困难
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
提示：
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
"""


"""
讲解一下使用单调栈的解法。
遍历高度数组 height。
如果当前柱体高度较小，小于等于栈顶柱体的高度，则将当前柱子高度入栈。
如果当前柱体高度较大，大于栈顶柱体的高度，则一直出栈，直到当前柱体小于等于栈顶柱体的高度。
假设当前柱体为 C，出栈柱体为 B，出栈之后新的栈顶柱体为 A。则说明：
当前柱体 C 是出栈柱体 B 向右找到的第一个大于当前柱体高度的柱体，那么以出栈柱体 B 为中心，可以向右将宽度扩展到当前柱体 C。
新的栈顶柱体 A 是出栈柱体 B 向左找到的第一个大于当前柱体高度的柱体，那么以出栈柱体 B 为中心，可以向左将宽度扩展到当前柱体 A。
出栈后，以新的栈顶柱体 A 为左边界，以当前柱体 C 为右边界，以左右边界与出栈柱体 B 的高度差为深度，计算可以接到雨水的面积。然后记录并更新累积面积。
"""

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        stack = []
        size = len(height)

        for i in range(size):
            while stack and height[i] > height[stack[-1]]:
                curr = stack.pop(-1)

                if stack:
                    left = stack[-1] + 1
                    right = i - 1
                    heigh = min(height[i], height[stack[-1]]) - height[curr]
                    ans += heigh *(right - left + 1)

                else:
                    break
            stack.append(i)
        return ans



# 方法二：  动态规划
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        n = len(height)
        leftMax = [height[0]] + [0] * (n-1)
        for i in range(1, n):
            leftMax[i] =max(leftMax[i-1], height[i])
        rightMax = [0] * (n-1) + [height[n-1]]
        for i in range(n-2, -1, -1):
            rightMax[i] = max(rightMax[i+1], height[i])
        
        ans = sum(min(leftMax[i], rightMax[i]) - height[i] for i in range(n))
        return ans
